package leetcode.code;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 63. 不同路径 II
 *
 * @author CaoYu
 * @date 2021年10月15日
 * @description
 */
public class Solution0063 implements IDebug {

	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int r = obstacleGrid.length;
		int c = obstacleGrid[0].length;
		int[][] dp = new int[r + 1][c + 1];
		dp[r][c - 1] = 1;
		for (int i = r - 1; i >= 0; i--) {
			for (int j = c - 1; j >= 0; j--) {
				if (obstacleGrid[i][j] == 0) {
					dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
				}
			}
		}
		return dp[0][0];
	}

	public int uniquePathsWithObstacles3(int[][] obstacleGrid) {
		int r = obstacleGrid.length;
		int c = obstacleGrid[0].length;
		int[][] dp = new int[r + 1][c + 1];
		dp[r - 1][c - 1] = 1;
		for (int i = r - 1; i >= 0; i--) {
			for (int j = c - 1; j >= 0; j--) {
				if (obstacleGrid[i][j] == 0) {
					dp[i][j] += dp[i + 1][j] + dp[i][j + 1];
				}
			}
		}
		return dp[0][0];
	}

	public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
		int r = obstacleGrid.length;
		int c = obstacleGrid[0].length;
		if (obstacleGrid[r - 1][c - 1] == 1 || obstacleGrid[0][0] == 1)// 终点 or 起点上放了个石头, 可还行
			return 0;
		int[][] dp = new int[r][c];
		dp[r - 1][c - 1] = 1;
		for (int i = r - 1; i >= 0; i--) {
			for (int j = c - 1; j >= 0; j--) {
				dp[i][j] += i + 1 < r && obstacleGrid[i + 1][j] == 0 ? dp[i + 1][j] : 0;// 从下边来的方式数量
				dp[i][j] += j + 1 < c && obstacleGrid[i][j + 1] == 0 ? dp[i][j + 1] : 0;// 从右边来的方式数量
			}
		}
		return dp[0][0];
	}

	public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
		return this.f(obstacleGrid, 0, 0);
	}

	private int f(int[][] grid, int i, int j) {
		if (i == grid.length - 1 && j == grid[0].length - 1) {
			return 1;
		}
		int ans = 0;
		if (i + 1 < grid.length && grid[i + 1][j] == 0) {
			ans += this.f(grid, i + 1, j);
		}
		if (j + 1 < grid[0].length && grid[i][j + 1] == 0) {
			ans += this.f(grid, i, j + 1);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution0063 so = new Solution0063();
		so.debug1();
		so.debug2();
	}

	@Override
	public void debug1() {
		String str = "[[0,0,0],[0,1,0],[0,0,0]]";
		int e = 2;
		int r = this.uniquePathsWithObstacles(HelpDebug.str2array1(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[[0,1],[0,0]]";
		int e = 1;
		int r = this.uniquePathsWithObstacles(HelpDebug.str2array1(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

}
